6.1 KB · ⇊ 2 parts · ⤓ Micron 6.1 KB · ⤓ HTML 24.9 KB

layout: Wide · Narrow · Centered

top

In quantum computing, the hidden shift problem is a type of oracle-based problem. Various versions of this problem have quantum algorithms which can run much more quickly than known non-quantum methods for the same problem. In its general form, it is equivalent to the hidden subgroup problem for the dihedral group.cite-ref-cvd05-1-0[1] It is a major open problem to understand how well quantum algorithms can perform for this task, as it can be applied to break lattice-based cryptography.cite-ref-2[2]cite-ref-3[3]

• Problem statement

• Algorithms

• References

The hidden shift problem states: Given an oracle O {\displaystyle O} that encodes two functions f {\displaystyle f} and g {\displaystyle g} , there is an n {\displaystyle n} -bit string s {\displaystyle s} for which g ( x ) = f ( x + s ) {\displaystyle g(x)=f(x+s)} for all x {\displaystyle x} . Find s {\displaystyle s} .cite-ref-wh02-4-0[4]

Functions such as the Legendre symbol and bent functions, satisfy these constraints.cite-ref-5[5]

With a quantum algorithm that is defined as | s ⟩ = H ⊗ n O f H ⊗ n O g ^ H ⊗ n | 0 n ⟩ {\displaystyle |s\rangle =H^{\otimes n}O_{f}H^{\otimes n}O_{\hat {g}}H^{\otimes n}|0^{n}\rangle } , where H {\displaystyle H} is the Hadamard gate and g ^ {\displaystyle {\hat {g}}} is the Fourier transform of g {\displaystyle g} , certain instantiations of this problem can be solved in a polynomial number of queries to O {\displaystyle O} while taking exponential queries with a classical algorithm.

cite-note-cvd05-11. ↑ citerefchildsvan-dam2007Childs, Andrew M.; van Dam, Wim (2007), "Quantum algorithm for a generalized hidden shift problem", in Bansal, Nikhil; Pruhs, Kirk; Stein, Clifford (eds.), Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, SIAM, pp. 1225–1232, arXiv:quant-ph/0507190

cite-note-22. ↑ citereflomont2004Lomont, Chris (November 4, 2004), The Hidden Subgroup Problem - Review and Open Problems, arXiv:quant-ph/0411037

cite-note-33. ↑ citerefregev2004Regev, Oded (January 2004). "Quantum Computation and Lattice Problems". SIAM Journal on Computing. 33 (3): 738–760. doi:10.1137/S0097539703440678. ISSN 0097-5397.

cite-note-wh02-44. ↑ citerefdamhallgrenip2002Dam, Wim van; Hallgren, Sean; Ip, Lawrence (2002). "Quantum Algorithms for some Hidden Shift Problems". SIAM Journal on Computing. 36 (3): 763–778. arXiv:quant-ph/0211140. doi:10.1137/S009753970343141X. S2CID 11122780.

cite-note-55. ↑ citerefr-tteler2008Rötteler, Martin (2008). "Quantum algorithms for highly non-linear Boolean functions". Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. Vol. 402. Society for Industrial and Applied Mathematics. pp. 448–457. arXiv:0811.3208. doi:10.1137/1.9781611973075.37. ISBN 978-0-89871-701-3. S2CID 9615826.